/*************************************************************************
	> File Name: 微软100题-005.cpp
	> Author: ma6174
	> Mail: ma6174@163.com 
	> Created Time: Sun 02 Jun 2013 06:33:29 PM CST
 ************************************************************************/

#include<iostream>
#include <iterator>
#include <cstdlib>
#include <cassert>
using namespace std;

/*
 * 查找最小的 k 个元素(数组)
 * 题目:输入 n 个整数,输出其中最小的 k 个。
 * 例如输入 1,2,3,4,5,6,7 和 8 这 8 个数字,则最小的 4 个数字为 1,2,3 和 4。
 *
 */

////////////////////////////////////////////////////////
class Heap {
	int n;
	int *array;

	public:
	Heap(int array[], int n) {
		this->n = n;
		this->array = new int[n];
		std::copy(array, array+n, this->array);
		BuildHeap();
	}

	void BuildHeap();

	int PerDown();

	bool IsEmpty() {return n == 0; }
};

/*
 * 使用堆的方法，建立一个小顶堆
 */
void
Heap::BuildHeap() {
	int i, select;
	for (i = (n-1) / 2; i >= 0; --i) {
		select = (i*2 + 1);
		if (select+1 < n && array[select] > array[select+1])
			select += 1;
		std::cout << "select: " << select << endl;
		if (array[select] < array[i])
			swap<int>(array[select], array[i]);
	}
}

int
Heap::PerDown() {
	assert(n != 0);
	//std::copy(array, array+n, ostream_iterator<int>(cout, " "));
	cout << endl;

	int retValue = array[0];
	array[0] = array[n-1];
	--n;

	int k = 0, select;
	while(k < n) {
		select = k*2 +1;
		if (select >= n) break;
		if (select + 1 < n && array[select] > array[select+1])
			select += 1;
		if (select < n && array[k] > array[select])
			swap<int>(array[k], array[select]);
		k = select;
	}
	return retValue;
}
////////////////////////////////////////////////////////


////////////////////////////////////////////////////////
/*
 * 在[left, right]中找前nth
 */
int
Partition(int array[], int left, int right) {
	int pivot;
	int l, r;

	pivot = array[left];
	l = left;
	r = right;
	while(l < r) {
		while(r > l && array[r] > pivot)
			r--;
		if (r > l)
			array[l] = array[r], l++;
		while(l < r && array[l] < pivot)
			l++;
		if (r > l)
			array[r] = array[l], r--;
	}
	array[l] = pivot;
	return l - left;
}


void FindNthLittle(int array[], int n, int k) {
	int l, r;
	l = 0, r = n-1;
	while(true) {
		int nth = Partition(array, l, r); 
		if (nth + 1< k) {
			l = l + nth + 1;
			r = r;
			k = k - (nth + 1);
		} else if (nth + 1 > k) {
			l = l;
			r = l + nth;
			k = k;
		} else {
			break;
		}
	}
}


/*
 * n个数的一种随机排列
 */
void
GetRndArray(int array[], int n) {
	assert(array != NULL && n > 0);

	srand(time(NULL));

	int swapSrc, swapDst;
	for (int i = 0; i < n; ++i) {
		swapSrc = i;
		swapDst = random() % (n - i) + i;
		swap<int>(array[swapSrc], array[swapDst]);
	}
}


int
main(int argc, char *argv[]) {
	int array[] = {1, 2, 3, 4, 5, 6, 7, 8};
	int n = sizeof(array)/sizeof(array[0]);
	int k = 4;
	GetRndArray(array, n);
	copy(array, array+n, ostream_iterator<int>(cout, " "));
	cout << endl;
	/*
	Heap heap(array, sizeof(array)/sizeof(array[0]));
	while(!heap.IsEmpty())
			cout << heap.PerDown() << endl;
	*/

	FindNthLittle(array, n, k);
	copy(array, array+k, ostream_iterator<int>(cout, " "));
	cout << endl;

	return 0;
}
